Round Overview
Discuss this match
The key observation is that the choices of songs are independent for each idol. This means that if an idol is assigned a song, this will not stop other idols from being assigned whatever other song. The reason is that each song can only be performed by one specific idol, so there will never be a case in which two idols compete for a song assignment.
Since each idol is an independent story, we should consider each idol and their available songs independently. There might be multiple songs available for an idol and they must sing only one of them. It’s most convenient to pick the song with the maximum happiness.
The rest is implementation. In this case it needs extra work because idols are identified by strings and the strings are only used to identify the idol allowed for each song.
We can first get a list of all the unique idol names. Then for each of the idol names, find the maximum h[i] for an i such that s[i] is equal to the idol name. Like in the following Java and python solutions:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.io.*;
import java.util.*;
public class LiveConcert {
public int maxHappiness(int[] h, String[] s) {
// Using a Set and Collections.add to get the set of unique idols,
// we can do this manually but builtin functions really help:
Set < String > unique = new HashSet < String > ();
Collections.addAll(unique, s);
int sum = 0;
// for each unique idol:
for (String idol: unique) {
int best = 0;
// best happiness of a song assignable to idol:
for (int i = 0; i < h.length; i++) {
if (s[i].equals(idol)) {
best = Math.max(best, h[i]);
}
}
sum += best;
}
return sum;
}
}
1 2 3 4 5 6 7 8 9 10
class LiveConcert: def maxHappiness(self, h, s): def get_idol_max(idol): return max(hi for (hi, si) in zip(h, s) if (si == idol)) unique_idols = set(s) return sum(get_idol_max(idol) for idol in unique_idols)
Another idea is to use an associative array (map, dictionary, Hash table) so you can store the best happiness for each idol using the idol as a key. Like in the following c++ solution using std::map :
1
2
3
4
5
6
7
8
9
10
11
12
13
int maxHappiness(vector < int > h, vector < string > s) {
map < string, int > idol_sings;
// for each song:
for (int i = 0; i < h.size(); i++) {
// remember the best song for each idol
idol_sings[s[i]] = std::max(idol_sings[s[i]], h[i]);
}
int sum = 0;
for (auto q: idol_sings) {
sum += q.second;
}
return sum;
}
CombiningSlimes
Problem Details
The maximization problem is a bit of a trick question, because no matter what order we pick to combine the slimes, the final score will always be the same. You can find this by trying with three slimes of sizes a, b and c.
Merge b and c then merge with a: The first merge will have score bc and yield a slime of size b+c which is then merged with a for score a(b+c). The result is bc + ab + ac.
Merge a and b then the result with c: ab + (a + b)c.
Merge a with c then the result with b: ac + (a+ c)b.
In any of the strategies the score is ab + ac + bc. More so this is the score you’d get by adding the product of every unordered pair of slime sizes.
Let’s use a proof by induction. We know that this will be true for n = 2 and n = 3. Now let’s ask: Assuming that this is true for all n < t, can we show it to be true for t?
Given t slimes the last move will involve merging two last slimes. This means that there are two groups of slimes such that each group will become one of the two last slimes to merge. Assume the first group consists of a slimes x_1, x_2, …, x_a and the second group of b slimes: y_1, y_2, …, y_b. The optimal scores when merging each of the groups will be the sum of the products of every unordered pair: sum_(i<j)(x_i * x_j) and sum_(i<j)(y_i * y_j). What is the score for the last step? The sizes of the two last slimes will be: x_1 + x_2 + … + x_a and y_1 + y_2 + … + y_b. The score of the last move will be: (x_1 + x_2 + … + x_a)(y_1 + y_2 + … + y_b), the product will be equal to the sum of the products of all pairs of two slimes from distinct groups. This combined to the other sums will be a sum of all possible unordered distinct pairs of slimes.
Now all that we need is to grab the slime sizes and calculate the sum of the products of all unordered pairs of slimes:
1
2
3
4
5
6
7
8
9
int maxMascots(vector < int > a) {
int sum = 0;
for (int i = 0; i < a.size(); i++) {
for (int j = i + 1; j < a.size(); j++) {
sum += a[i] * a[j];
}
}
return sum;
}
The problem statement asks us to find all graphs and add all of their Line MSTs. We can swap the logic. How about for all Line MSTs, we add all the graphs that contain them? The result will be the same.
All line MSTs will be similar, only the order of the vertices in the line will vary: 0-1-2-3 is a line MST, as is 3-1-2-0. The number of complete graphs that contain a specific MST doesn’t vary with that order. So we can just calculate it for a simple line MST 0-1-2-…-(n-1), and multiply it by the number of ways to change its order. There are n! ways to reorder 0,1,2,…,n-1, note that lines like 0-1-2-3 and 3-2-1-0 are really the same tree, so n! will double count each possible line. In order to account for this we need to divide by 2: (n!)/2.
Now we want to count the number of complete graphs that can contain 0-1-2-…-(n-1) as a line MST. The graphs are always complete so what we are counting is the number of ways to assign costs to the edges. In this version of the problem the two possible costs are 1 and 2. The maximum number of vertices is n. So there will be at most 15 edges connecting the vertices in the line MST. There are at most 2^15 different ways to assign costs to these edges. How about we try them all, and for each of them we count the number of graphs?
So we start with some assignment of edge costs in the line MST:
We need to count the number of ways there are to pick costs for the other edges. We should understand that each of the edges in the MST introduces a condition. Pick one edge in the MST, without this edge, there would be two connected components.
In a complete graph, there will be edges connecting all the possible pairs of vertices from each component:
Any of these edges connecting the two components can be used instead of our edge and the result would be a spanning tree. If any of those edges was smaller than our edge, the resulting tree would have a smaller weight and thus our intended line wouldn’t be the minimum spanning tree. So we want all edges connecting these two components to have a weight larger than or equal to our wanted edge’s weight. These edges may be equal, because that way there will be multiple MSTs in the graph, and the intended line will be one of them. When the edge we want has weight 1, this isn’t important, because all edges will have a weight that is larger or equal. But when the edge’s weight is 2, then it is important: For each i, if edge i -> (i+1) in line MST has weight 2, then all edges u <-> v, where u <= i and v > i must have a weight equal to 2.
Each edge in the line MST, might restrict the values of some edges so that their weight cannot be 1. At the end, of all the available edges, some will be allowed to be 1 or 2, and some will be forced to be 2. Just multiply the result by 2 for each edge that is allowed to be 1 or 2. That is our solution.
Problems that ask you to return the result modulo 1,000,000,007 (or a similar number) usually do so to allow us to solve problems that have large results without actually using those large numbers in calculations. We can handle these numbers with modular arithmetic. Read this recipe for more info.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const int MOD = 1000000007;
int count(int N) {
long res = 0;
for (int mask = 0; mask < (1 << (N - 1)); mask++) {
long graphs = 1;
vector < vector < int >> min_edge(N, vector < int > (N, 1));
for (int i = 0; i < N - 1; i++) {
// MST edge connecting i with (i+1)
int e = ((mask & (1 << i)) ? 2 : 1);
if (e == 2) {
// restriction for all those edges:
for (int u = 0; u <= i; u++) {
for (int v = i + 1; v < N; v++) {
min_edge[u][v] = 2;
}
}
}
}
// multiply as needed:
for (int i = 0; i < N; i++) {
for (int j = i + 2; j < N; j++) {
if (min_edge[i][j] == 1) {
graphs = (graphs * 2) % MOD;
}
}
}
// multiply by N! / 2 = (2*3*4*...*N) = (3*4*...*N), note N >= 2
for (int i = 3; i <= N; i++) {
graphs = (graphs * i) % MOD;
}
// add to total
res += graphs;
}
return (int)(res % MOD);
}
SubdividedSlimes
Problem Details
If we can find, given k, the maximum score possible then we can find the minimum k for which the score is at least M. In that case, we can use a simple linear search for k. A binary search would also be possible but won’t be necessary in this problem.
Given k how do you maximize the score? An intermediary step is to first think of the final result. The final result will be some slimes of some sizes. Given the sizes, can we calculate the score?
For k=1, there will be two slimes, let their sizes be a and b. There is just one cut so the score is ab.
k=2, 3 slimes with sizes a, b and c. There are two ways to cut the slimes. One way is to cut into a and b+c then cut b+c into c. The score is: a(b + c) + bc = ab + ac + bc. The other method yields (a+b)c + ab = ac + bc + ab, exactly the same.
For k=3, it will be the same: ab + ac + ad + bc + bd + cd. For each pair of final slime sizes, the product of the two sizes is added to the score.
A proof for general k, using induction. We know this is true for k=1. Prove that if it is true for all values smaller than k, then it’s also true for k: Imagine the slime sizes will be: x_0, x_1, …, x_k, we pick a position i where we make the first cut. This cuts the case in two parts: x_0, x_1, … , x_i and x_(i+1), x_(i+2), … , x_k. The score of the first cut will be: (x_0 + x_1 +…+ x_i)( x_(i+1) + x_(i+2) + … + x_k ) which is just the sum of all products of pairs between the two groups of sizes. The rest of the score is equal to the optimal scores of each of the groups, which will be the sum of products of all pairs of sizes in each group.
The important thing is that the final slime sizes determine the score. The order of the cuts doesn’t matter. And the formula is easy like : ab + ac + … az + bc + bd + … For a given k, we need to pick the k+1 final sizes that will maximize the score. If you want to maximize the sum ab + ac + ad + bc + bd + cd, given that a + b + c + d = S, this is an application of Lagrange multipliers. In short, the optimal result is reached when a = b = c = d = S/4. In our problem, S will be a integer and cuts can only be integer, but we can still approximate that the best result comes from dividing the slimes as evenly as possible.
Note that the formula is good only to find the strategy that maximizes the score, but computationally, it’s less expensive to calculate the score cut by cut as originally. We need O(S) for the number of cuts and each k needs an O(k) process to get the score when cutting as evenly as possible. In total O(S^2).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int needCut(int S, int M) {
// try a k, find the maximum score:
for (int k = 1; k <= S - 1; k++) {
int x = S; // current slime
int r = 0;
for (int i = k; i >= 1; i--) {
if (x >= 1) {
int d = x / (i + 1);
// next slime cut is of size d
r += d * (x - d);
x -= d;
}
}
if (r >= M) {
return k;
}
}
return -1;
}
It will help to read the explanation for the division 2 version. We will use the same idea, counting all the graphs that contain Line MST 0-1-…-(n-1) and multiplying by (n!)/2. The difference is that now n can be up to 200 and so can the maximum edge weight.
Let’s say that we decided the weight w for edge connecting i and i+1. This edge is used to connect two components: One containing vertices 0 to i and the other containing vertices i+1 to n-1. All of the (i+1) times (n-i-1) edges connecting these two components must have a weight greater than or equal to w, one of them, the one connecting i and i+1 already has weight w. A useful thing is that after dealing with these edges, the two components can be dealt with separately. In each of the two components, we need to first create a complete graph, one with i+1 vertices and the other with n-i+1 vertices. In each of them, we want a specific line MST, in one we want 0,1,2,…,i, and in the other i+1, i+2, … , n-1, but we can relabel those vertices as 0, 1, … so we can solve this smaller problem using the same method as the original one.
We now have an idea on how the problem can be divided in two MSTs, but we need to give some shape to this idea. We do not want an approach that counts duplicated graphs. Let’s take edge i -> i+1. If we assign w to this edge, we will also count the number of ways to have a smaller MST, but we don’t want the smaller MST with indexes 0,1,2,…,i+1, to be able to pick w as one of its edges, because that case would have been considered before. So what we can do is represent the solution by a function f(n, w), which counts the number of ways to have 0,1,2,…,n-1 as a line MST where w is the maximum allowed weight we can use as an edge in the MST (Note that L is still the limit for the edges that are not in the MST):
There are some base cases: n <= 2 can be calculated in a case-by case basis. w cannot be 0, that would mean we cannot use any edge in the line MST, because weights must be at least 1.
It is possible that none of the edges in the line MST has weight w. Then we we should say that the edges will all be smaller, thus the result should be equal to f(n,w-1).
In another case, some edges will have weight w. So we decide the smallest index edge i -> (i+1) that will have weight w. Note that edges with greater indexes may also have that same weight.
The (i+1) times (n-i-1) - 1 connecting the two components that are not in the MST must all have a weight >= w, this means that we have (i+1) times (n-i-1) - 1 decisions, each with L - w + 1 options: (L - w + 1) ^ ((i+1) times (n-i-1) - 1) ways in total to decide those edges.
The first i+1 vertices make a subgraph, we want the line MST here, but we cannot use edges of weight w: There are f(i+1, w-1) ways to do this.
The other n-i-1 vertices also make a subgraph that needs to have a line MST, but this time they are allowed to have edges of weight w: f(n-i-1, w)
The product f(i+1, w-1) * f(n-i-1, w) * (L - w + 1) ^ ((i+1) times (n-i-1) - 1) is the number of graphs when edge i -> i+1 has weight w. We should add this for all i, this would be the number of graphs that have weight w in their line MST. From above we also know that f(n,w-1) is the number of graphs that don’t have weight w. Combine them for the answer.
The result is a recurrence relation f(n,w) with O(N L) possible states, each needs an O(N) loop to add up for all i. Since f(n,w) always depends on results f(i,w-1) and f(n-i-1,w) where, the new number of vertices is smaller, then the recurrence relation is acyclic so we can solve it using iterative dynamic programming. In total, the time complexity is O(N^2 L).
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
const int MOD = 1000000007;
long mod_pow(long x, long y) {
long res = 1;
while (y > 0) {
if (y % 2 == 1) {
res = (res * x) % MOD;
}
x = (x * x) % MOD;
y /= 2;
}
return res;
}
int N, L;
long dp[201][201];
long f(int n, int max_cost) {
long & res = dp[n][max_cost];
if (res == -1) {
if (n <= 1) {
res = 1; //only one graph with 1 or 0 nodes
} else if (n <= 2) {
// connect the two nodes with an edge
res = max_cost;
} else if (max_cost == 0) {
res = 0;
} else {
res = f(n, max_cost - 1);
for (int i = 0; i + 1 < n; i++) {
// edge between i -> i+1, is the first one with cost max_cost
long p = f(i + 1, max_cost - 1);
long q = f(n - i - 1, max_cost);
long r = mod_pow(L - max_cost + 1, (i + 1) * (n - i - 1) - 1);
res += (((p * q) % MOD) * r) % MOD;
}
}
res %= MOD;
}
return res;
}
int count(int N, int L) {
this - > N = N;
this - > L = L;
memset(dp, -1, sizeof(dp));
long res = f(N, L);
for (int i = 3; i <= N; i++) {
res = (res * i) % MOD;
}
return (int)(res);
}